package leetcode100

// TODO 递归+回溯+剪枝 [经典] 【-】 组合总和
// TODO https://leetcode.cn/problems/combination-sum/solution/shou-hua-tu-jie-zu-he-zong-he-combination-sum-by-x/

func combinationSum(candidates []int, target int) [][]int {
	res := [][]int{}

	var dfs func(start int, temp []int, sum int)
	dfs = func(start int, temp []int, sum int) {
		// 剪枝: 递归结束控制器
		if sum >= target {
			if sum == target {
				// 下面两条语句就是为了创建一个 新的切片 放入 Slice
				newTmp := make([]int, len(temp))
				copy(newTmp, temp)
				res = append(res, newTmp)
			}
			return
		}
		// 递归
		for i := start; i < len(candidates); i++ {
			temp = append(temp, candidates[i])
			dfs(i, temp, sum+candidates[i])
			// 回溯
			temp = temp[:len(temp)-1]
		}
	}
	dfs(0, []int{}, 0)
	return res
}
